package btree;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-10-21
 * Time:23:56
 */
public class MyBtree {
    static class BTRNode {
        public int[] keys;
        public BTRNode[] subs;
        public BTRNode parent;
        public int usedSize;

        public BTRNode() {
            //多给一个，方便分裂
            this.keys = new int[M];
            this.subs = new BTRNode[M+1];
        }
    }
    public static final int M = 3;
    public BTRNode root;

    /**
     * 插入一个元素
     * @param key
     * @return
     */
    public boolean insert(int key) {
        //1. b树为空的时候
        if (root == null) {
            root = new BTRNode();
            root.keys[0] = key;
            root.usedSize++;
            return true;
        }
        //2.b树不为空的时候，需要查看当前b树中是否存在该key
        Pair<BTRNode, Integer> pair = find(key);
        if (pair.getVal() != -1) {
            //存在该key
            return false;
        }

        //3.如果不存在该key，则进行插入
        BTRNode parent = pair.getKey();
        int i = parent.usedSize - 1;
        for (; i >= 0 ; i--) {
            if (parent.keys[i] >= key) {
                parent.keys[i + 1] = parent.keys[i];
            } else {
                break;
            }
        }
        parent.keys[i + 1] = key;
        parent.usedSize++;
        if (parent.usedSize < M) {
            return true;
        }
        //满了 分裂
        split(parent);
        return true;
    }

    /**
     * 分裂
     * @param cur 当前需要分裂的节点
     */
    private void split(BTRNode cur) {
        BTRNode newNode = new BTRNode();
        //1.先存储当前需要分裂节点的父节点
        BTRNode parent = cur.parent;
        //2.开始挪数据
        int mid = cur.usedSize >> 1;
        int i = mid + 1;
        int j = 0;
        for (; i < cur.usedSize; i++) {
            newNode.keys[j] = cur.keys[i];
            newNode.subs[j] = cur.subs[i];
            //处理靠过来的孩子节点的父亲节点 为newNode
            if (newNode.subs[j] != null) {
                newNode.subs[j].parent = newNode;
            }
            j++;
        }
        //多拷贝一次孩子
        newNode.subs[j] = cur.subs[i];
        if (newNode.subs[j] != null) {
            newNode.subs[j].parent = newNode;
        }
        //更新当前新节点的有效数据
        newNode.usedSize = j;
        cur.usedSize = cur.usedSize - j - 1;
        //处理根节点的情况
        if (cur == root) {
            root = new BTRNode();
            root.keys[0] = cur.keys[mid];
            root.subs[0] = cur;
            root.subs[1] = newNode;
            root.usedSize = 1;
            cur.parent = root;
            newNode.parent = root;
            return;
        }
        newNode.parent = parent;
        //移动父亲节点
        int endT = parent.usedSize - 1;
        int midVal = cur.keys[mid];
        for (; endT >= 0; endT--) {
            if (parent.keys[endT] >= midVal) {
                parent.keys[endT + 1] = parent.keys[endT];
                parent.subs[endT + 2] = parent.subs[endT + 1];
            } else {
                break;
            }
        }
        parent.keys[endT + 1] = midVal;
        parent.subs[endT + 2] = newNode;
        parent.usedSize++;
        if (parent.usedSize >= M) {
            split(parent);
        }

    }

    private Pair<BTRNode, Integer> find(int key) {
        BTRNode cur = root;
        BTRNode parent = null;
        while (cur != null) {
            int i = 0;
            while (i < cur.usedSize) {
                if (cur.keys[i] == key) {
                    //返回一个当前找到的节点和当前这个数据在节点当中的下标
                    return new Pair<>(cur, i);
                } else if (cur.keys[i] < key) {
                    i++;
                } else {
                    break;
                }
            }
            parent = cur;
            cur = cur.subs[i];
        }
        return new Pair<>(parent, -1);
    }
}
